// @algorithm @lc id=678 lang=cpp 
// @title valid-parenthesis-string


#define print(...)
// @test("()")=true
// @test("(*)")=true
// @test("(*))")=true
// @test("(")=false
// @test("(((((()*)(*)*))())())(()())())))((**)))))(()())()")=false
class Solution {
public:
    bool checkValidString(string s) {
        list<int> stkLeft, stkStar;
        print("input=", s, "\n")
        for(int i=0; i<s.size(); i++){
            switch(s[i]){
            case '(':
                stkLeft.push_back(i);
                break;
            case '*':
                stkStar.push_back(i);
                break;
            case ')':
                if(!stkLeft.empty())
                    stkLeft.pop_back();
                else if(!stkStar.empty())
                    stkStar.pop_back();
                else
                    return false;
            }
            print(s[i], "| left=", stkLeft, ", star=", stkStar, "\n")
        }
        while(stkLeft.size() && stkStar.size()){
            if(stkLeft.back() >= stkStar.back())
                return false;
            stkLeft.pop_back();
            stkStar.pop_back();
        }
        print(", size:", stkLeft.size(), ", ", stkStar.size(), "\n")
        return stkLeft.empty();
    }
};